/*
题目描述：寻找二叉树的下一个节点
条件：给出当前节点，然后返回前序遍历的下一个节点
方法：
分两种情况：当前节点有右子树时，下一个节点在当前节点的右子树的最左子树
           当前节点没有右子树时，需要回退，找到一个当前节点的父节点满足该父节点为其父节点的左子树，返回该父节点的父节点
 */
class TreeNode{
    char value;
    TreeNode left;
    TreeNode right;
    TreeNode parent;
    TreeNode(char c){
        this.value = c;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

public class E8 {
    public static void main(String[] args){
        //inorder: d,b,h,e,i,a,f,c,g
        TreeNode node1 = new TreeNode('a');
        TreeNode node2 = new TreeNode('b');
        TreeNode node3 = new TreeNode('c');
        TreeNode node4 = new TreeNode('d');
        TreeNode node5 = new TreeNode('e');
        TreeNode node6 = new TreeNode('f');
        TreeNode node7 = new TreeNode('g');
        TreeNode node8 = new TreeNode('h');
        TreeNode node9 = new TreeNode('i');
        node1.parent = null; node1.left = node2; node1.right = node3;
        node2.parent = node1; node2.left = node4; node2.right = node5;
        node3.parent = node1; node3.left = node6; node3.right = node7;
        node4.parent = node2; node4.left = node4.right = null;
        node5.parent = node2; node5.left = node8; node5.right = node9;
        node6.parent = node3; node6.left = node6.right =  null;
        node7.parent = node3; node7.left = node7.right = null;
        node8.parent = node5; node8.left = node8.right = null;
        node9.parent = node5; node9.left = node9.right;

        System.out.println("inorder: [d,b,h,e,i,a,f,c,g]");

        System.out.println("a next = " + GetNext(node1).value);
        System.out.println("b next = " + GetNext(node2).value);
        System.out.println("c next = " + GetNext(node3).value);
        System.out.println("d next = " + GetNext(node4).value);
        System.out.println("e next = " + GetNext(node5).value);
        System.out.println("f next = " + GetNext(node6).value);
        if(GetNext(node7) == null){
            System.out.println("g next = " + "null");
        }
        else{
            System.out.println("g next = " + GetNext(node7).value);
        }
        System.out.println("h next = " + GetNext(node8).value);
        System.out.println("i next = " + GetNext(node9).value);

    }

    private static TreeNode GetNext(TreeNode node){
        if(node == null){
            return null;
        }
        TreeNode next = null;
        if(node.right != null){
            TreeNode right = node.right;
            while(right.left != null){
                right = right.left;
            }
            next = right;
        }
        else if(node.parent != null){
            TreeNode curNode = node;
            TreeNode curParent = node.parent;
            while(curParent != null && curParent.left != curNode){
                curNode = curParent;
                curParent = curParent.parent;
            }
            next = curParent;
        }
        return next;
    }
}
/*
inorder: [d,b,h,e,i,a,f,c,g]
a next = f
b next = h
c next = g
d next = b
e next = i
f next = c
g next = null
h next = e
i next = a
 */